本场链接:Educational Codeforces Round 73

闲话

这场VP出了A~D.但是猜的成分挺高的.

A. 2048 Game

题目大意:给定一个$n$个数的集合,保证其内所有的元素都是$2$的幂.每次你可以从中选出两个数,并把他们俩的和作为新元素放进原集合.而原来的两个数被删掉.问是否能出现2048.只用输出是否.

数据范围:
$1 \leq n \leq 100$

思路

乱搞即可.规定一个目标,初始为2048,每次看目标的值的数量够不够,如果不够的话就把目标拆解一半,再算新的目标是否足够.注意如果原序列里有原来的目标值,则所需的数量会减少.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pil;
#define x first
#define y second
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		map<ll,int> cnt;
		for(int i = 1;i <= n;++i)	
		{
			ll x;scanf("%lld",&x);
			++cnt[x];
		}
		int target = 2048,ok = 0,need = 1;
		while(target >= 1)
		{
			if(cnt[target] >= need)	
			{
				// cout << target << " " << cnt[target] << endl;
				ok = 1;
				break;
			}
			need -= cnt[target];
			target /= 2;
			need *= 2;
			
		}
		if(!ok)	puts("NO");
		else puts("YES");
    }
    return 0;
}

B. Knights

题目大意:一个$n*n$的棋盘上放置若干个棋子,每个棋子是两种颜色中的一个.棋子按"日"字型攻击.构造一种摆放方案,使得整个棋局上颜色不同且可以互相攻击到的棋子对的数量最多.

思路

对于每一个点来说,如果他的八个方向的点都是跟他颜色不同的,则自然就是最多的.因此联想到二分图的染色,对这个图一样的处理,即使得颜色不同且互相攻击到的对数最多.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
char g[N][N];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= n;++j)
			if((i + j) & 1)	g[i][j] = 'W';
			else g[i][j] = 'B';
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j)
			printf("%c",g[i][j]);
		puts("");
	}
    return 0;
}

C. Perfect Team

题目大意:三种类型的零件各有$a,b,c$个,一个机器里要有恰好三个零件,其中$a,b$零件的数量不得少于$1$.问最多能组合出多少种.

思路

显然应该先满足$c$的情况,在组合$abc$的前提下算出一个结果,之后问题就又等价成了只有$ab$的时候有多少种组合方式.由于此时$a,b$的类型没有什么区别,因此可以交换使得$a \leq b$.这个时候还有两种构造机器的方式:一种是$aab$另一种是$bba$.假设在最后的答案里,前者有$x$个后者有$y$个,那么显然答案就是$x+y$,根据不等式关系有$x+y \leq \frac{a+b}{3}$.但是答案不是直接加上这个数就结束了的,因为还有一个极端情况:如果此时$b \geq 2*a$的话,原来的不等式的右侧就有:$\frac{a+b}{3} \leq \frac{3a}{3} = a$即此时如果选择$a$答案可能会变得更好,这是一个特殊情况,需要额外考虑.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {	
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		int res = 0;
		res += min({a,b,c});
		a -= res;b -= res;c -= res;
		if(a > b)	swap(a,b);
		if(a * 2 <= b)
		{
			res += a;
			b -= a;
			a = 0;
		}
		else res += (a + b) / 3;

		printf("%d\n",res);
    }
    return 0;
}

D. Make The Fence Great Again

题目大意:有$n$个元素,每个元素有两个属性$a$和$b$,$b$表示如果要让$a$增加$1$所要付出的代价.现在要使整个序列里不存在相邻的两个元素的$a$值相同.问最小化费是多少.

思路

这个题一拿到手会发现非常像$dp$.但是由于数的范围会导致整个空间开不够,而且也不能靠滚动数组优化空间.因此思路就断了,如果继续想贪心构造会发现这个题也没什么突破口.dp关键的一个问题就是值域太大了,那么有没有办法使第二维的值域变小呢?答案是肯定的.
对于每个元素来说,他的$a$值增加的次数是不超过$2$的,关于这一点可以手推验证.只要运用这个性质,就可以把第二维的空间压下来了.
状态:$f[i][j]$表示当前在$i$元素上,这个元素要增加$j$次.
入口:$f[1][0] = 0,f[1][1] = b[1],f[1][2] = 2 * b[1]$
转移:当且仅当$a[i] + j \neq a[i - 1] + k$时,$f[i][j] = min(f[i][j],f[i - 1][k] + j * b[i])$
出口:$\min({f[n][0],f[n][1],f[n][2]})$
注意,本题的答案范围是$2^{18}$,这意味着要开$LL$.不过这还不是重点,重点是$INF$即$f$数组的初值一定要根据类型设置大小,因为这里是$LL$所以设置的是$2^{60}$如果开成$2^{30}$就会WA.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 3e5+7,INF = (1ll << 60);
int a[N],b[N],f[N][3];
signed main()
{
    int T;scanf("%lld",&T);
    while(T--)
    {
		int n;scanf("%lld",&n);
    	for(int i = 1;i <= n;++i)	scanf("%lld%lld",&a[i],&b[i]);
		f[1][0] = 0;f[1][1] = b[1];f[1][2] = 2 * b[1];
    	for(int i = 2;i <= n;++i)
    		for(int j = 0;j <= 2;++j)
    		{
    			f[i][j] = INF;
				for(int k = 0;k <= 2;++k)
					if(a[i - 1] + k != a[i] + j)
						f[i][j] = min(f[i][j],f[i - 1][k] + j * b[i]);
    		}
    	printf("%lld\n",min({f[n][0],f[n][1],f[n][2]}));
    }
    return 0;
}